package com.example.leetdemo.finash;

import java.util.*;

public class Solution658 {

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> result = new ArrayList<>();
        if (x < arr[0]) {
            for (int i = 0; i < k; i++) {
                result.add(arr[i]);
            }
        } else if (x > arr[arr.length - 1]) {

            for (int i = arr.length - 1; i > Math.max(0, arr.length - k - 1); i--) {
                result.add(arr[i]);
            }
            Collections.reverse(result);
        } else {
            int target = binarySearch(arr, x);
            int left = target - 1, right = target + 1;
            int[] temp = new int[k];
            temp[0] = arr[target];
            for (int i = 1; i < k; i++) {
                if (right > arr.length - 1) {
                    temp[i] = arr[left];
                    left--;
                } else if (left < 0) {
                    temp[i] = arr[right];
                    right++;
                } else if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
                    temp[i] = arr[right];
                    right++;
                } else {
                    temp[i] = arr[left];
                    left--;
                }
            }
            Arrays.sort(temp);
            for (int i = 0; i < temp.length; i++) {
                result.add(temp[i]);
            }
        }

        return result;
    }

    private int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int result = Math.abs(arr[left] - target) > Math.abs(arr[right] - target) ?  right : left;
        while (right - left != 1) {
            int mid = (right - left) / 2 + left;
            if (target < arr[mid]) {
                right = mid;
            }
            if (target == arr[mid]) {
                result = mid;
                break;
            }
            if (target > arr[mid]) {
                left = mid;
            }
            result = Math.abs(arr[left] - target) > Math.abs(arr[right] - target) ?  right : left;
        }
//        result = Math.abs(arr[left] - target) > Math.abs(arr[right] - target) ?  right : left;
        return result;
    }

    public static void main(String[] args) {
        Solution658 solution658 = new Solution658();
//        solution658.findClosestElements(new int[] {0,0,1,2,3,3,4,7,7,8}, 3, 5);
        System.err.println(Integer.reverse(21));

        Map<Integer, Integer> map = new HashMap<>();
//        System.err.println(Math.abs(2 - 4) > Math.abs(7 - 4));
    }
}
